#@Time : 2021/11/815:04
#@Author : xujian

# 请定义一个队列并实现函数 max_value 得到队列里的最大值，
# 要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
# 若队列为空，pop_front 和 max_value 需要返回 -1

# 如何理解题意：其实就是每次向队列中加一个数字
import queue
from collections import deque
class MaxQueue:

    def __init__(self):
        self.q1=queue.Queue()
        self.q2=deque()
    def max_value(self) -> int:
        #就是返回q2的第一个元素
        if self.q2 == None:return -1
        return self.q2[0]
    def push_back(self, value: int) -> None:
        self.q1.put(value)
        #来个while循环删除q2中小于value的值
        while self.q2 and self.q2[-1]<value:
            self.q2.pop()
        #把这个value弄进q2
        self.q2.append(value)

    def pop_front(self) -> int:
        #你要从前面删除d1的元素，需要使用get()方法
        val=self.q1.get()
        #如果要删除的正好最大值，需要更新q2
        if val==self.q2[0]:
            self.q2.popleft()
        return val    #返回删除的元素



m1=MaxQueue()
m1.push_back(10)
m1.push_back(9)
m1.push_back(2)
m1.push_back(0)
print(m1.max_value())
print(m1.pop_front())
print(m1.pop_front())
print(m1.max_value())
# print(m1.pop_front())
# print(m1.pop_front())
# print(m1.pop_front())

#我编列一下queue
print("===========")
#结束的条件不好找鸭？？？？？？？？？？？？？？？
# while(True):
#     print(m1.queue.get())





